/*
 * EditDistanceGazetteer.java
 *
 */
package edu.columbia.gate.plugins;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import gate.*;
import gate.corpora.DocumentContentImpl;
import gate.creole.*;
import gate.creole.gazetteer.*;
import gate.persist.PersistenceException;
import gate.security.SecurityException;
import gate.util.*;


/** This component is responsible for doing lists lookup. The implementaion is
 * based on finite state machines.
 * The phrases to be recognised should be listed in a set of files, one for
 * each type of occurences.
 * The gazeteer is build with the information from a file that contains the set
 * of lists (which are files as well) and the associated type for each list.
 * The file defining the set of lists should have the following syntax:
 * each list definition should be written on its own line and should contain:
 * <ol>
 * <li>the file name (required) </li>
 * <li>the major type (required) </li>
 * <li>the minor type (optional)</li>
 * <li>the language(s) (optional) </li>
 * </ol>
 * The elements of each definition are separated by &quot;:&quot;.
 * The following is an example of a valid definition: <br>
 * <code>personmale.lst:person:male:english</code>
 * Each list file named in the lists definition file is just a list containing
 * one entry per line.
 * When this gazetter will be run over some input text (a Gate document) it
 * will generate annotations of type Lookup having the attributes specified in
 * the definition file.
 */
public class EditDistanceGazetteer extends AbstractEditDistanceGazetteer
{


	/**
	 * Build a gazetter using the default lists from the gate resources
	 */
	public EditDistanceGazetteer()
	{
	}

	/** Does the actual loading and parsing of the lists. This method must be
	 * called before the gazetteer can be used
	 */
	public Resource init() throws ResourceInstantiationException
	{
		if (listsURL == null)
		{
			throw new ResourceInstantiationException(
					"No URL provided for gazetteer creation!");
		}
		vocabulary = new Hashtable<String, EditDistanceLookup>();
		if(globalMatchCache == null)
		{
			globalMatchCache = new Hashtable<String, Hashtable<String,MatchEntryData>>();
			matchCache = new Hashtable<String, MatchEntryData>();
		}
		else if(globalMatchCache.contains(listsURL.toString()))
		{
			matchCache = globalMatchCache.get(listsURL.toString()); 
			System.out.println("EditDistanceGazetteer.init - Reusing matchCache.");
		}
		else
		{
			matchCache = new Hashtable<String, MatchEntryData>();
		}
		globalMatchCache.put(listsURL.toString(), matchCache);
		
		majorTypesPriorities = new Hashtable<String, Integer>();
		
		definition = new LinearDefinition();
		definition.setSeparator(Strings.unescape(gazetteerFeatureSeparator));
		definition.setURL(listsURL);
		definition.load();
		int linesCnt = definition.size();
		listsByNode = definition.loadLists();
		Iterator inodes = definition.iterator();
		minEntryLength = Integer.MAX_VALUE;
		maxEntryLength = 0;

		int nodeIdx = 0;
		LinearNode node;
		while (inodes.hasNext())
		{
			node = (LinearNode) inodes.next();
			fireStatusChanged("Reading " + node.toString());
			fireProgressChanged(++nodeIdx * 100 / linesCnt);
			readList(node, true);
		} // while iline
		fireProcessFinished();
		return this;
	}


	/**
	 * This method runs the gazetteer. It assumes that all the needed parameters
	 * are set. If they are not, an exception will be fired.
	 */
	public void execute() throws ExecutionException
	{
		interrupted = false;
		AnnotationSet annotationSet;
		//check the input
		if (document == null)
		{
			throw new ExecutionException("No document to process!");
		}

		sortedVocabulary = new ArrayList<Map.Entry<String,EditDistanceLookup>>();
		sortedVocabulary.addAll(vocabulary.entrySet());
		Collections.sort(sortedVocabulary, new LookupComparator());

		if (annotationSetName == null || annotationSetName.equals(""))
			annotationSet = document.getAnnotations();
		else
			annotationSet = document.getAnnotations(annotationSetName);

		fireStatusChanged("Performing look-up in " + document.getName() + "...");
		
		ArrayList<Unigram> unigrams = this.getUnigrams(annotationSet);

		int oldCharIdx = 0;
		int matchedRegionEnd = 0;
		int matchedRegionStart = 0;
		int length = document.getContent().size().intValue();

		MatchEntryData match = null;
		int i = 0;
		while (i < unigrams.size())
		{
			Unigram unigram = unigrams.get(i);

			match = new MatchEntryData();
			match.sourceWord = unigram.word;

			
			if (lookupInVocabulary(match))
			{
				matchedRegionStart = unigram.start;
				matchedRegionEnd = unigram.end;
				match.lookup.features.put(FEATURE_NAME_ENTRY_MATCHED,
						match.lookup.translation);
				match.lookup.features.put(FEATURE_NAME_EDIT_DISTANCE, new Double(
						match.getEditDistance()));
				createLookups(match.lookup, matchedRegionStart, matchedRegionEnd,
						annotationSet);
			}


			//Report percentage of progress 
			if (matchedRegionEnd - oldCharIdx > 256)
			{
				fireProgressChanged((100 * matchedRegionEnd) / length);
				if (isInterrupted())
					throw new ExecutionInterruptedException(
							"The execution of the "
									+ getName()
									+ " gazetteer has been abruptly interrupted!");
			}

			i ++;
		}

		fireProcessFinished();
		fireStatusChanged("Look-up complete!");
	} // execute

	private boolean lookupInVocabulary(MatchEntryData match)
	{
		MatchEntryData imatch = null;

		imatch = matchCache.get(match.sourceWord);
		if (imatch != null)
		{
			imatch.copyTo(match);
			return true;
		}
		if( ((double)(minEntryLength - match.sourceWord.length())) / ((double) match.sourceWord.length()) > maxEditDistance
			|| ((double)(minEntryLength - match.sourceWord.length())) / minEntryLength > maxEditDistance
			|| ((double)(match.sourceWord.length() - maxEntryLength)) / ((double) match.sourceWord.length()) > maxEditDistance
			|| ((double)(match.sourceWord.length() - maxEntryLength)) / maxEntryLength > maxEditDistance)
		{
			return false;
		}
		match.dlDistance = (int) Math.ceil(maxEditDistance
				* match.sourceWord.length());
		
		String targetWord = null;
		boolean success = false;
		EditDistanceLookup lookup;
		lookup = vocabulary.get(match.sourceWord);

		if(lookup != null)
		{
			match.dlDistance = 0;
			match.targetWord = match.sourceWord;
			match.lookup = lookup;
			success = true;
		}
		else
		{	
			imatch = match.clone();
			for (Map.Entry<String, EditDistanceLookup> mapEntry : sortedVocabulary)
			{
				targetWord = mapEntry.getKey();
				imatch.targetWord = targetWord;
				lookup = mapEntry.getValue();
				imatch.lookup = lookup;
	
				damerauLevenshteinDistance(imatch);
				
				// Is the editDistance acceptable?
				if(imatch.getEditDistance() < maxEditDistance
					&& imatch.getEditDistance() < match.getEditDistance())				
				{
					imatch.copyTo(match);
					success = true;
				}
			}
			if (success)
			{
				matchCache.put(match.sourceWord, match);
			}
		}
		return success;
	}

	void damerauLevenshteinDistance(MatchEntryData match)
	{

		String str1 = match.targetWord;
		String str2 = match.sourceWord;
		int lenStr1 = str1.length();
		int lenStr2 = match.sourceWord.length();

		// d is a table with lenStr1+1 rows and lenStr2+1 columns
		int[][] d = new int[lenStr1 + 1][lenStr2 + 1];
		int substCost = 1, insertCost = 1, deletCost = 1, transCost = 1;
		int scost, tcost;

		// i and j are used to iterate over str1 and match.sourceWord
		int i, j;

		for (i = 0; i <= lenStr1; i++)
			d[i][0] = i;
		for (j = 1; j <= lenStr2; j++)
			d[0][j] = j;

		for (i = 1; i <= lenStr1; i++)
		{
			boolean isDistanceTooFar = true;
			for (j = 1; j <= lenStr2; j++)
			{
				if (str1.charAt(i - 1) == match.sourceWord.charAt(j - 1))
				{
					tcost = 0;
					scost = 0;
				} else
				{
					scost = substCost;
					tcost = transCost;
				}
				int deletion = d[i - 1][j] + deletCost; // deletion
				int insertion = d[i][j - 1] + insertCost; // insertion
				int substitution = d[i - 1][j - 1] + scost; // substitution
				// Take the minimum
				d[i][j] = (deletion <= insertion ? deletion : insertion) <= substitution ? (deletion <= insertion ? deletion
						: insertion)
						: substitution;

				// transposition
				if (i > 1 && j > 1 && str1.charAt(i - 1) == match.sourceWord.charAt(j - 2)
						&& str1.charAt(i - 2) == str2.charAt(j - 1))
				{
					// Take the minimum
					d[i][j] = d[i][j] <= (d[i - 2][j - 2] + tcost) ? d[i][j]
							: (d[i - 2][j - 2] + tcost);
				}
				if(isDistanceTooFar
						&& ((double) d[i][j]) / ((double) lenStr1) <= maxEditDistance 
						&& ((double) d[i][j]) / ((double) lenStr2) <= maxEditDistance) 
					isDistanceTooFar = false;
			}
			if(isDistanceTooFar)
			{
				match.dlDistance = Integer.MAX_VALUE;
				return;
			}
		}

		match.dlDistance = (int) d[lenStr1][lenStr2];
	}

	/**
	 * Creates the EditDistanceLookup annotations according to a gazetteer match.
	 * @param matchingState the final EditDistanceFSMState that was reached while matching.
	 * @param matchedRegionStart the start of the matched text region.
	 * @param matchedRegionEnd the end of the matched text region.
	 * @param annotationSet the annotation set where the new annotations should
	 * be added.
	 */
	protected void createLookups(EditDistanceLookup currentLookup,
			long matchedRegionStart, long matchedRegionEnd,
			AnnotationSet annotationSet)
	{
		FeatureMap fm = Factory.newFeatureMap();
		fm.put(LOOKUP_MAJOR_TYPE_FEATURE_NAME, currentLookup.majorType);
		if (null != currentLookup.oClass && null != currentLookup.ontology)
		{
			fm.put(LOOKUP_CLASS_FEATURE_NAME, currentLookup.oClass);
			fm.put(LOOKUP_ONTOLOGY_FEATURE_NAME, currentLookup.ontology);
		}

		if (null != currentLookup.minorType)
			fm.put(LOOKUP_MINOR_TYPE_FEATURE_NAME, currentLookup.minorType);
		if (null != currentLookup.features)
		{
			fm.putAll(currentLookup.features);
		}
		try
		{
			annotationSet.add(new Long(matchedRegionStart), new Long(
					matchedRegionEnd), LOOKUP_ANNOTATION_TYPE, fm);
		} catch (InvalidOffsetException ioe)
		{
			throw new GateRuntimeException(ioe.toString());
		}
	}

	/** A set containing all the states of the FSM backing the gazetteer
	 */
	protected Set fsmStates;

	/**lookup <br>
	 * @param singleItem a single string to be looked up by the gazetteer
	 * @return set of the Lookups associated with the parameter*/
	public Set lookup(String singleItem)
	{
		Set set = new HashSet();
		singleItem = singleItem.toUpperCase();
		MatchEntryData match = new MatchEntryData(singleItem);
		if (lookupInVocabulary(match))
		{
			set.add(match.lookup);
		}
		return set;
	}

	public boolean remove(String singleItem)
	{
		EditDistanceLookup lookup = vocabulary.remove(singleItem.toUpperCase());
		return (lookup == null);
	}

	public boolean add(String singleItem, Lookup lookup)
	{
		EditDistanceLookup lookup2;
		if (lookup instanceof EditDistanceLookup)
			lookup2 = (EditDistanceLookup) lookup;
		else
			lookup2 = new EditDistanceLookup(lookup);

		singleItem = singleItem.toUpperCase().replaceAll("\\s+", " ");
		vocabulary.put(singleItem, lookup2);

		return true;
	}

	/**
	 * @return the gazetteerFeatureSeparator
	 */
	public String getGazetteerFeatureSeparator()
	{
		return gazetteerFeatureSeparator;
	}

	/**
	 * @param gazetteerFeatureSeparator the gazetteerFeatureSeparator to set
	 */
	public void setGazetteerFeatureSeparator(String gazetteerFeatureSeparator)
	{
		this.gazetteerFeatureSeparator = gazetteerFeatureSeparator;
	}

	/**
	 * @return the maxEditDistance
	 */
	public Double getMaxEditDistance()
	{
		return new Double(maxEditDistance);
	}

	/**
	 * @param maxEditDistance the maxEditDistance to set
	 */
	public void setMaxEditDistance(Double maxEditDistance)
	{
		this.maxEditDistance = maxEditDistance.doubleValue();
	}

} // EditDistanceGazetteer
